/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.util.concurrent;

import static com.google.common.base.Preconditions.checkNotNull;
import static java.util.Objects.requireNonNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.MapMaker;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.Weak;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.EnumMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.annotation.CheckForNull;

/**
 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and {@link
 * ReentrantReadWriteLock} instances that detect potential deadlock by checking for cycles in lock
 * acquisition order.
 *
 * <p>Potential deadlocks detected when calling the {@code lock()}, {@code lockInterruptibly()}, or
 * {@code tryLock()} methods will result in the execution of the {@link Policy} specified when
 * creating the factory. The currently available policies are:
 *
 * <ul>
 *   <li>DISABLED
 *   <li>WARN
 *   <li>THROW
 * </ul>
 *
 * <p>The locks created by a factory instance will detect lock acquisition cycles with locks created
 * by other {@code CycleDetectingLockFactory} instances (except those with {@code Policy.DISABLED}).
 * A lock's behavior when a cycle is detected, however, is defined by the {@code Policy} of the
 * factory that created it. This allows detection of cycles across components while delegating
 * control over lock behavior to individual components.
 *
 * <p>Applications are encouraged to use a {@code CycleDetectingLockFactory} to create any locks for
 * which external/unmanaged code is executed while the lock is held. (See caveats under
 * <strong>Performance</strong>).
 *
 * <p><strong>Cycle Detection</strong>
 *
 * <p>Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
 * example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
 * then Lock B, while another thread acquires Lock B, and then Lock A:
 *
 * <pre>
 * Thread1: acquire(LockA) --X acquire(LockB)
 * Thread2: acquire(LockB) --X acquire(LockA)
 * </pre>
 *
 * <p>Neither thread will progress because each is waiting for the other. In more complex
 * applications, cycles can arise from interactions among more than 2 locks:
 *
 * <pre>
 * Thread1: acquire(LockA) --X acquire(LockB)
 * Thread2: acquire(LockB) --X acquire(LockC)
 * ...
 * ThreadN: acquire(LockN) --X acquire(LockA)
 * </pre>
 *
 * <p>The implementation detects cycles by constructing a directed graph in which each lock
 * represents a node and each edge represents an acquisition ordering between two locks.
 *
 * <ul>
 *   <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
 *       Thread acquires its first hold (and releases its last remaining hold).
 *   <li>Before the lock is acquired, the lock is checked against the current set of acquired
 *       locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either
 *       verified or created.
 *   <li>If a new edge needs to be created, the outgoing edges of the acquired locks are traversed
 *       to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new
 *       "safe" edge is created.
 *   <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential
 *       deadlock situation, and the appropriate Policy is executed.
 * </ul>
 *
 * <p>Note that detection of potential deadlock does not necessarily indicate that deadlock will
 * happen, as it is possible that higher level application logic prevents the cyclic lock
 * acquisition from occurring. One example of a false positive is:
 *
 * <pre>
 * LockA -&gt; LockB -&gt; LockC
 * LockA -&gt; LockC -&gt; LockB
 * </pre>
 *
 * <p><strong>ReadWriteLocks</strong>
 *
 * <p>While {@code ReadWriteLock} instances have different properties and can form cycles without
 * potential deadlock, this class treats {@code ReadWriteLock} instances as equivalent to
 * traditional exclusive locks. Although this increases the false positives that the locks detect
 * (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and
 * implementation considerably. The assumption is that a user of this factory wishes to eliminate
 * any cyclic acquisition ordering.
 *
 * <p><strong>Explicit Lock Acquisition Ordering</strong>
 *
 * <p>The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used to enforce an
 * application-specific ordering in addition to performing general cycle detection.
 *
 * <p><strong>Garbage Collection</strong>
 *
 * <p>In order to allow proper garbage collection of unused locks, the edges of the lock graph are
 * weak references.
 *
 * <p><strong>Performance</strong>
 *
 * <p>The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
 * Benchmarks (as of December 2011) show that:
 *
 * <ul>
 *   <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting lock takes 38ns as
 *       opposed to the 24ns taken by a plain lock.
 *   <li>for nested locking, the cost increases with the depth of the nesting:
 *       <ul>
 *         <li>2 levels: average of 64ns per lock()/unlock()
 *         <li>3 levels: average of 77ns per lock()/unlock()
 *         <li>4 levels: average of 99ns per lock()/unlock()
 *         <li>5 levels: average of 103ns per lock()/unlock()
 *         <li>10 levels: average of 184ns per lock()/unlock()
 *         <li>20 levels: average of 393ns per lock()/unlock()
 *       </ul>
 * </ul>
 *
 * <p>As such, the CycleDetectingLockFactory may not be suitable for performance-critical
 * applications which involve tightly-looped or deeply-nested locking algorithms.
 *
 * @author Darick Tong
 * @since 13.0
 */
@Beta
@CanIgnoreReturnValue // TODO(cpovirk): Consider being more strict.
@GwtIncompatible
@ElementTypesAreNonnullByDefault
public class CycleDetectingLockFactory
{

    /**
     * Encapsulates the action to be taken when a potential deadlock is encountered. Clients can use
     * one of the predefined {@link Policies} or specify a custom implementation. Implementations must
     * be thread-safe.
     *
     * @since 13.0
     */
    @Beta
    public interface Policy
    {

        /**
         * Called when a potential deadlock is encountered. Implementations can throw the given {@code
         * exception} and/or execute other desired logic.
         *
         * <p>Note that the method will be called even upon an invocation of {@code tryLock()}. Although
         * {@code tryLock()} technically recovers from deadlock by eventually timing out, this behavior
         * is chosen based on the assumption that it is the application's wish to prohibit any cyclical
         * lock acquisitions.
         */
        void handlePotentialDeadlock(PotentialDeadlockException exception);
    }

    /**
     * Pre-defined {@link Policy} implementations.
     *
     * @since 13.0
     */
    @Beta
    public enum Policies implements Policy
    {
        /**
         * When potential deadlock is detected, this policy results in the throwing of the {@code
         * PotentialDeadlockException} indicating the potential deadlock, which includes stack traces
         * illustrating the cycle in lock acquisition order.
         */
        THROW
                {
                    @Override
                    public void handlePotentialDeadlock(PotentialDeadlockException e)
                    {
                        throw e;
                    }
                },

        /**
         * When potential deadlock is detected, this policy results in the logging of a {@link
         * Level#SEVERE} message indicating the potential deadlock, which includes stack traces
         * illustrating the cycle in lock acquisition order.
         */
        WARN
                {
                    @Override
                    public void handlePotentialDeadlock(PotentialDeadlockException e)
                    {
                        logger.log(Level.SEVERE, "Detected potential deadlock", e);
                    }
                },

        /**
         * Disables cycle detection. This option causes the factory to return unmodified lock
         * implementations provided by the JDK, and is provided to allow applications to easily
         * parameterize when cycle detection is enabled.
         *
         * <p>Note that locks created by a factory with this policy will <em>not</em> participate the
         * cycle detection performed by locks created by other factories.
         */
        DISABLED
                {
                    @Override
                    public void handlePotentialDeadlock(PotentialDeadlockException e)
                    {
                    }
                };
    }

    /**
     * Creates a new factory with the specified policy.
     */
    public static CycleDetectingLockFactory newInstance(Policy policy)
    {
        return new CycleDetectingLockFactory(policy);
    }

    /**
     * Equivalent to {@code newReentrantLock(lockName, false)}.
     */
    public ReentrantLock newReentrantLock(String lockName)
    {
        return newReentrantLock(lockName, false);
    }

    /**
     * Creates a {@link ReentrantLock} with the given fairness policy. The {@code lockName} is used in
     * the warning or exception output to help identify the locks involved in the detected deadlock.
     */
    public ReentrantLock newReentrantLock(String lockName, boolean fair)
    {
        return policy == Policies.DISABLED
                ? new ReentrantLock(fair)
                : new CycleDetectingReentrantLock(new LockGraphNode(lockName), fair);
    }

    /**
     * Equivalent to {@code newReentrantReadWriteLock(lockName, false)}.
     */
    public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName)
    {
        return newReentrantReadWriteLock(lockName, false);
    }

    /**
     * Creates a {@link ReentrantReadWriteLock} with the given fairness policy. The {@code lockName}
     * is used in the warning or exception output to help identify the locks involved in the detected
     * deadlock.
     */
    public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName, boolean fair)
    {
        return policy == Policies.DISABLED
                ? new ReentrantReadWriteLock(fair)
                : new CycleDetectingReentrantReadWriteLock(new LockGraphNode(lockName), fair);
    }

    // A static mapping from an Enum type to its set of LockGraphNodes.
    private static final ConcurrentMap<
            Class<? extends Enum<?>>, Map<? extends Enum<?>, LockGraphNode>>
            lockGraphNodesPerType = new MapMaker().weakKeys().makeMap();

    /**
     * Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}.
     */
    public static <E extends Enum<E>> WithExplicitOrdering<E> newInstanceWithExplicitOrdering(
            Class<E> enumClass, Policy policy)
    {
        // createNodes maps each enumClass to a Map with the corresponding enum key
        // type.
        checkNotNull(enumClass);
        checkNotNull(policy);
        @SuppressWarnings("unchecked")
        Map<E, LockGraphNode> lockGraphNodes = (Map<E, LockGraphNode>) getOrCreateNodes(enumClass);
        return new WithExplicitOrdering<>(policy, lockGraphNodes);
    }

    @SuppressWarnings("unchecked")
    private static <E extends Enum<E>> Map<? extends E, LockGraphNode> getOrCreateNodes(
            Class<E> clazz)
    {
        Map<E, LockGraphNode> existing = (Map<E, LockGraphNode>) lockGraphNodesPerType.get(clazz);
        if (existing != null)
        {
            return existing;
        }
        Map<E, LockGraphNode> created = createNodes(clazz);
        existing = (Map<E, LockGraphNode>) lockGraphNodesPerType.putIfAbsent(clazz, created);
        return MoreObjects.firstNonNull(existing, created);
    }

    /**
     * For a given Enum type, creates an immutable map from each of the Enum's values to a
     * corresponding LockGraphNode, with the {@code allowedPriorLocks} and {@code
     * disallowedPriorLocks} prepopulated with nodes according to the natural ordering of the
     * associated Enum values.
     */
    @VisibleForTesting
    static <E extends Enum<E>> Map<E, LockGraphNode> createNodes(Class<E> clazz)
    {
        EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz);
        E[] keys = clazz.getEnumConstants();
        int numKeys = keys.length;
        ArrayList<LockGraphNode> nodes = Lists.newArrayListWithCapacity(numKeys);
        // Create a LockGraphNode for each enum value.
        for (E key : keys)
        {
            LockGraphNode node = new LockGraphNode(getLockName(key));
            nodes.add(node);
            map.put(key, node);
        }
        // Pre-populate all allowedPriorLocks with nodes of smaller ordinal.
        for (int i = 1; i < numKeys; i++)
        {
            nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i));
        }
        // Pre-populate all disallowedPriorLocks with nodes of larger ordinal.
        for (int i = 0; i < numKeys - 1; i++)
        {
            nodes.get(i).checkAcquiredLocks(Policies.DISABLED, nodes.subList(i + 1, numKeys));
        }
        return Collections.unmodifiableMap(map);
    }

    /**
     * For the given Enum value {@code rank}, returns the value's {@code "EnumClass.name"}, which is
     * used in exception and warning output.
     */
    private static String getLockName(Enum<?> rank)
    {
        return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
    }

    /**
     * A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the additional enforcement of
     * an application-specified ordering of lock acquisitions. The application defines the allowed
     * ordering with an {@code Enum} whose values each correspond to a lock type. The order in which
     * the values are declared dictates the allowed order of lock acquisition. In other words, locks
     * corresponding to smaller values of {@link Enum#ordinal()} should only be acquired before locks
     * with larger ordinals. Example:
     *
     * <pre>{@code
     * enum MyLockOrder {
     *   FIRST, SECOND, THIRD;
     * }
     *
     * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory =
     *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW);
     *
     * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST);
     * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND);
     * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD);
     *
     * lock1.lock();
     * lock3.lock();
     * lock2.lock();  // will throw an IllegalStateException
     * }</pre>
     *
     * <p>As with all locks created by instances of {@code CycleDetectingLockFactory} explicitly
     * ordered locks participate in general cycle detection with all other cycle detecting locks, and
     * a lock's behavior when detecting a cyclic lock acquisition is defined by the {@code Policy} of
     * the factory that created it.
     *
     * <p>Note, however, that although multiple locks can be created for a given Enum value, whether
     * it be through separate factory instances or through multiple calls to the same factory,
     * attempting to acquire multiple locks with the same Enum value (within the same thread) will
     * result in an IllegalStateException regardless of the factory's policy. For example:
     *
     * <pre>{@code
     * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 =
     *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
     * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 =
     *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
     *
     * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST);
     * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST);
     * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST);
     *
     * lockA.lock();
     *
     * lockB.lock();  // will throw an IllegalStateException
     * lockC.lock();  // will throw an IllegalStateException
     *
     * lockA.lock();  // reentrant acquisition is okay
     * }</pre>
     *
     * <p>It is the responsibility of the application to ensure that multiple lock instances with the
     * same rank are never acquired in the same thread.
     *
     * @param <E> The Enum type representing the explicit lock ordering.
     * @since 13.0
     */
    @Beta
    public static final class WithExplicitOrdering<E extends Enum<E>>
            extends CycleDetectingLockFactory
    {

        private final Map<E, LockGraphNode> lockGraphNodes;

        @VisibleForTesting
        WithExplicitOrdering(Policy policy, Map<E, LockGraphNode> lockGraphNodes)
        {
            super(policy);
            this.lockGraphNodes = lockGraphNodes;
        }

        /**
         * Equivalent to {@code newReentrantLock(rank, false)}.
         */
        public ReentrantLock newReentrantLock(E rank)
        {
            return newReentrantLock(rank, false);
        }

        /**
         * Creates a {@link ReentrantLock} with the given fairness policy and rank. The values returned
         * by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the lock in
         * warning or exception output.
         *
         * @throws IllegalStateException If the factory has already created a {@code Lock} with the
         *                               specified rank.
         */
        public ReentrantLock newReentrantLock(E rank, boolean fair)
        {
            return policy == Policies.DISABLED
                    ? new ReentrantLock(fair)
                    // requireNonNull is safe because createNodes inserts an entry for every E.
                    // (If the caller passes `null` for the `rank` parameter, this will throw, but that's OK.)
                    : new CycleDetectingReentrantLock(requireNonNull(lockGraphNodes.get(rank)), fair);
        }

        /**
         * Equivalent to {@code newReentrantReadWriteLock(rank, false)}.
         */
        public ReentrantReadWriteLock newReentrantReadWriteLock(E rank)
        {
            return newReentrantReadWriteLock(rank, false);
        }

        /**
         * Creates a {@link ReentrantReadWriteLock} with the given fairness policy and rank. The values
         * returned by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the
         * lock in warning or exception output.
         *
         * @throws IllegalStateException If the factory has already created a {@code Lock} with the
         *                               specified rank.
         */
        public ReentrantReadWriteLock newReentrantReadWriteLock(E rank, boolean fair)
        {
            return policy == Policies.DISABLED
                    ? new ReentrantReadWriteLock(fair)
                    // requireNonNull is safe because createNodes inserts an entry for every E.
                    // (If the caller passes `null` for the `rank` parameter, this will throw, but that's OK.)
                    : new CycleDetectingReentrantReadWriteLock(
                    requireNonNull(lockGraphNodes.get(rank)), fair);
        }
    }

    //////// Implementation /////////

    private static final Logger logger = Logger.getLogger(CycleDetectingLockFactory.class.getName());

    final Policy policy;

    private CycleDetectingLockFactory(Policy policy)
    {
        this.policy = checkNotNull(policy);
    }

    /**
     * Tracks the currently acquired locks for each Thread, kept up to date by calls to {@link
     * #aboutToAcquire(CycleDetectingLock)} and {@link #lockStateChanged(CycleDetectingLock)}.
     */
    // This is logically a Set, but an ArrayList is used to minimize the amount
    // of allocation done on lock()/unlock().
    private static final ThreadLocal<ArrayList<LockGraphNode>> acquiredLocks =
            new ThreadLocal<ArrayList<LockGraphNode>>()
            {
                @Override
                protected ArrayList<LockGraphNode> initialValue()
                {
                    return Lists.<LockGraphNode>newArrayListWithCapacity(3);
                }
            };

    /**
     * A Throwable used to record a stack trace that illustrates an example of a specific lock
     * acquisition ordering. The top of the stack trace is truncated such that it starts with the
     * acquisition of the lock in question, e.g.
     *
     * <pre>
     * com...ExampleStackTrace: LockB -&gt; LockC
     *   at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443)
     *   at ...
     *   at ...
     *   at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123)
     * </pre>
     */
    private static class ExampleStackTrace extends IllegalStateException
    {

        static final StackTraceElement[] EMPTY_STACK_TRACE = new StackTraceElement[0];

        static final ImmutableSet<String> EXCLUDED_CLASS_NAMES =
                ImmutableSet.of(
                        CycleDetectingLockFactory.class.getName(),
                        ExampleStackTrace.class.getName(),
                        LockGraphNode.class.getName());

        ExampleStackTrace(LockGraphNode node1, LockGraphNode node2)
        {
            super(node1.getLockName() + " -> " + node2.getLockName());
            StackTraceElement[] origStackTrace = getStackTrace();
            for (int i = 0, n = origStackTrace.length; i < n; i++)
            {
                if (WithExplicitOrdering.class.getName().equals(origStackTrace[i].getClassName()))
                {
                    // For pre-populated disallowedPriorLocks edges, omit the stack trace.
                    setStackTrace(EMPTY_STACK_TRACE);
                    break;
                }
                if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName()))
                {
                    setStackTrace(Arrays.copyOfRange(origStackTrace, i, n));
                    break;
                }
            }
        }
    }

    /**
     * Represents a detected cycle in lock acquisition ordering. The exception includes a causal chain
     * of {@code ExampleStackTrace} instances to illustrate the cycle, e.g.
     *
     * <pre>
     * com....PotentialDeadlockException: Potential Deadlock from LockC -&gt; ReadWriteA
     *   at ...
     *   at ...
     * Caused by: com...ExampleStackTrace: LockB -&gt; LockC
     *   at ...
     *   at ...
     * Caused by: com...ExampleStackTrace: ReadWriteA -&gt; LockB
     *   at ...
     *   at ...
     * </pre>
     *
     * <p>Instances are logged for the {@code Policies.WARN}, and thrown for {@code Policies.THROW}.
     *
     * @since 13.0
     */
    @Beta
    public static final class PotentialDeadlockException extends ExampleStackTrace
    {

        private final ExampleStackTrace conflictingStackTrace;

        private PotentialDeadlockException(
                LockGraphNode node1, LockGraphNode node2, ExampleStackTrace conflictingStackTrace)
        {
            super(node1, node2);
            this.conflictingStackTrace = conflictingStackTrace;
            initCause(conflictingStackTrace);
        }

        public ExampleStackTrace getConflictingStackTrace()
        {
            return conflictingStackTrace;
        }

        /**
         * Appends the chain of messages from the {@code conflictingStackTrace} to the original {@code
         * message}.
         */
        @Override
        public String getMessage()
        {
            // requireNonNull is safe because ExampleStackTrace sets a non-null message.
            StringBuilder message = new StringBuilder(requireNonNull(super.getMessage()));
            for (Throwable t = conflictingStackTrace; t != null; t = t.getCause())
            {
                message.append(", ").append(t.getMessage());
            }
            return message.toString();
        }
    }

    /**
     * Internal Lock implementations implement the {@code CycleDetectingLock} interface, allowing the
     * detection logic to treat all locks in the same manner.
     */
    private interface CycleDetectingLock
    {

        /**
         * @return the {@link LockGraphNode} associated with this lock.
         */
        LockGraphNode getLockGraphNode();

        /**
         * @return {@code true} if the current thread has acquired this lock.
         */
        boolean isAcquiredByCurrentThread();
    }

    /**
     * A {@code LockGraphNode} associated with each lock instance keeps track of the directed edges in
     * the lock acquisition graph.
     */
    private static class LockGraphNode
    {

        /**
         * The map tracking the locks that are known to be acquired before this lock, each associated
         * with an example stack trace. Locks are weakly keyed to allow proper garbage collection when
         * they are no longer referenced.
         */
        final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks =
                new MapMaker().weakKeys().makeMap();

        /**
         * The map tracking lock nodes that can cause a lock acquisition cycle if acquired before this
         * node.
         */
        final Map<LockGraphNode, PotentialDeadlockException> disallowedPriorLocks =
                new MapMaker().weakKeys().makeMap();

        final String lockName;

        LockGraphNode(String lockName)
        {
            this.lockName = Preconditions.checkNotNull(lockName);
        }

        String getLockName()
        {
            return lockName;
        }

        void checkAcquiredLocks(Policy policy, List<LockGraphNode> acquiredLocks)
        {
            for (LockGraphNode acquiredLock : acquiredLocks)
            {
                checkAcquiredLock(policy, acquiredLock);
            }
        }

        /**
         * Checks the acquisition-ordering between {@code this}, which is about to be acquired, and the
         * specified {@code acquiredLock}.
         *
         * <p>When this method returns, the {@code acquiredLock} should be in either the {@code
         * preAcquireLocks} map, for the case in which it is safe to acquire {@code this} after the
         * {@code acquiredLock}, or in the {@code disallowedPriorLocks} map, in which case it is not
         * safe.
         */
        void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock)
        {
            // checkAcquiredLock() should never be invoked by a lock that has already
            // been acquired. For unordered locks, aboutToAcquire() ensures this by
            // checking isAcquiredByCurrentThread(). For ordered locks, however, this
            // can happen because multiple locks may share the same LockGraphNode. In
            // this situation, throw an IllegalStateException as defined by contract
            // described in the documentation of WithExplicitOrdering.
            Preconditions.checkState(
                    this != acquiredLock,
                    "Attempted to acquire multiple locks with the same rank %s",
                    acquiredLock.getLockName());

            if (allowedPriorLocks.containsKey(acquiredLock))
            {
                // The acquisition ordering from "acquiredLock" to "this" has already
                // been verified as safe. In a properly written application, this is
                // the common case.
                return;
            }
            PotentialDeadlockException previousDeadlockException = disallowedPriorLocks.get(acquiredLock);
            if (previousDeadlockException != null)
            {
                // Previously determined to be an unsafe lock acquisition.
                // Create a new PotentialDeadlockException with the same causal chain
                // (the example cycle) as that of the cached exception.
                PotentialDeadlockException exception =
                        new PotentialDeadlockException(
                                acquiredLock, this, previousDeadlockException.getConflictingStackTrace());
                policy.handlePotentialDeadlock(exception);
                return;
            }
            // Otherwise, it's the first time seeing this lock relationship. Look for
            // a path from the acquiredLock to this.
            Set<LockGraphNode> seen = Sets.newIdentityHashSet();
            ExampleStackTrace path = acquiredLock.findPathTo(this, seen);

            if (path == null)
            {
                // this can be safely acquired after the acquiredLock.
                //
                // Note that there is a race condition here which can result in missing
                // a cyclic edge: it's possible for two threads to simultaneous find
                // "safe" edges which together form a cycle. Preventing this race
                // condition efficiently without _introducing_ deadlock is probably
                // tricky. For now, just accept the race condition---missing a warning
                // now and then is still better than having no deadlock detection.
                allowedPriorLocks.put(acquiredLock, new ExampleStackTrace(acquiredLock, this));
            }
            else
            {
                // Unsafe acquisition order detected. Create and cache a
                // PotentialDeadlockException.
                PotentialDeadlockException exception =
                        new PotentialDeadlockException(acquiredLock, this, path);
                disallowedPriorLocks.put(acquiredLock, exception);
                policy.handlePotentialDeadlock(exception);
            }
        }

        /**
         * Performs a depth-first traversal of the graph edges defined by each node's {@code
         * allowedPriorLocks} to find a path between {@code this} and the specified {@code lock}.
         *
         * @return If a path was found, a chained {@link ExampleStackTrace} illustrating the path to the
         * {@code lock}, or {@code null} if no path was found.
         */
        @CheckForNull
        private ExampleStackTrace findPathTo(LockGraphNode node, Set<LockGraphNode> seen)
        {
            if (!seen.add(this))
            {
                return null; // Already traversed this node.
            }
            ExampleStackTrace found = allowedPriorLocks.get(node);
            if (found != null)
            {
                return found; // Found a path ending at the node!
            }
            // Recurse the edges.
            for (Entry<LockGraphNode, ExampleStackTrace> entry : allowedPriorLocks.entrySet())
            {
                LockGraphNode preAcquiredLock = entry.getKey();
                found = preAcquiredLock.findPathTo(node, seen);
                if (found != null)
                {
                    // One of this node's allowedPriorLocks found a path. Prepend an
                    // ExampleStackTrace(preAcquiredLock, this) to the returned chain of
                    // ExampleStackTraces.
                    ExampleStackTrace path = new ExampleStackTrace(preAcquiredLock, this);
                    path.setStackTrace(entry.getValue().getStackTrace());
                    path.initCause(found);
                    return path;
                }
            }
            return null;
        }
    }

    /**
     * CycleDetectingLock implementations must call this method before attempting to acquire the lock.
     */
    private void aboutToAcquire(CycleDetectingLock lock)
    {
        if (!lock.isAcquiredByCurrentThread())
        {
            ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
            LockGraphNode node = lock.getLockGraphNode();
            node.checkAcquiredLocks(policy, acquiredLockList);
            acquiredLockList.add(node);
        }
    }

    /**
     * CycleDetectingLock implementations must call this method in a {@code finally} clause after any
     * attempt to change the lock state, including both lock and unlock attempts. Failure to do so can
     * result in corrupting the acquireLocks set.
     */
    private static void lockStateChanged(CycleDetectingLock lock)
    {
        if (!lock.isAcquiredByCurrentThread())
        {
            ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
            LockGraphNode node = lock.getLockGraphNode();
            // Iterate in reverse because locks are usually locked/unlocked in a
            // LIFO order.
            for (int i = acquiredLockList.size() - 1; i >= 0; i--)
            {
                if (acquiredLockList.get(i) == node)
                {
                    acquiredLockList.remove(i);
                    break;
                }
            }
        }
    }

    final class CycleDetectingReentrantLock extends ReentrantLock implements CycleDetectingLock
    {

        private final LockGraphNode lockGraphNode;

        private CycleDetectingReentrantLock(LockGraphNode lockGraphNode, boolean fair)
        {
            super(fair);
            this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
        }

        ///// CycleDetectingLock methods. /////

        @Override
        public LockGraphNode getLockGraphNode()
        {
            return lockGraphNode;
        }

        @Override
        public boolean isAcquiredByCurrentThread()
        {
            return isHeldByCurrentThread();
        }

        ///// Overridden ReentrantLock methods. /////

        @Override
        public void lock()
        {
            aboutToAcquire(this);
            try
            {
                super.lock();
            }
            finally
            {
                lockStateChanged(this);
            }
        }

        @Override
        public void lockInterruptibly() throws InterruptedException
        {
            aboutToAcquire(this);
            try
            {
                super.lockInterruptibly();
            }
            finally
            {
                lockStateChanged(this);
            }
        }

        @Override
        public boolean tryLock()
        {
            aboutToAcquire(this);
            try
            {
                return super.tryLock();
            }
            finally
            {
                lockStateChanged(this);
            }
        }

        @Override
        public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException
        {
            aboutToAcquire(this);
            try
            {
                return super.tryLock(timeout, unit);
            }
            finally
            {
                lockStateChanged(this);
            }
        }

        @Override
        public void unlock()
        {
            try
            {
                super.unlock();
            }
            finally
            {
                lockStateChanged(this);
            }
        }
    }

    final class CycleDetectingReentrantReadWriteLock extends ReentrantReadWriteLock
            implements CycleDetectingLock
    {

        // These ReadLock/WriteLock implementations shadow those in the
        // ReentrantReadWriteLock superclass. They are simply wrappers around the
        // internal Sync object, so this is safe since the shadowed locks are never
        // exposed or used.
        private final CycleDetectingReentrantReadLock readLock;
        private final CycleDetectingReentrantWriteLock writeLock;

        private final LockGraphNode lockGraphNode;

        private CycleDetectingReentrantReadWriteLock(LockGraphNode lockGraphNode, boolean fair)
        {
            super(fair);
            this.readLock = new CycleDetectingReentrantReadLock(this);
            this.writeLock = new CycleDetectingReentrantWriteLock(this);
            this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
        }

        ///// Overridden ReentrantReadWriteLock methods. /////

        @Override
        public ReadLock readLock()
        {
            return readLock;
        }

        @Override
        public WriteLock writeLock()
        {
            return writeLock;
        }

        ///// CycleDetectingLock methods. /////

        @Override
        public LockGraphNode getLockGraphNode()
        {
            return lockGraphNode;
        }

        @Override
        public boolean isAcquiredByCurrentThread()
        {
            return isWriteLockedByCurrentThread() || getReadHoldCount() > 0;
        }
    }

    private class CycleDetectingReentrantReadLock extends ReentrantReadWriteLock.ReadLock
    {

        @Weak
        final CycleDetectingReentrantReadWriteLock readWriteLock;

        CycleDetectingReentrantReadLock(CycleDetectingReentrantReadWriteLock readWriteLock)
        {
            super(readWriteLock);
            this.readWriteLock = readWriteLock;
        }

        @Override
        public void lock()
        {
            aboutToAcquire(readWriteLock);
            try
            {
                super.lock();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public void lockInterruptibly() throws InterruptedException
        {
            aboutToAcquire(readWriteLock);
            try
            {
                super.lockInterruptibly();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public boolean tryLock()
        {
            aboutToAcquire(readWriteLock);
            try
            {
                return super.tryLock();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException
        {
            aboutToAcquire(readWriteLock);
            try
            {
                return super.tryLock(timeout, unit);
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public void unlock()
        {
            try
            {
                super.unlock();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }
    }

    private class CycleDetectingReentrantWriteLock extends ReentrantReadWriteLock.WriteLock
    {

        @Weak
        final CycleDetectingReentrantReadWriteLock readWriteLock;

        CycleDetectingReentrantWriteLock(CycleDetectingReentrantReadWriteLock readWriteLock)
        {
            super(readWriteLock);
            this.readWriteLock = readWriteLock;
        }

        @Override
        public void lock()
        {
            aboutToAcquire(readWriteLock);
            try
            {
                super.lock();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public void lockInterruptibly() throws InterruptedException
        {
            aboutToAcquire(readWriteLock);
            try
            {
                super.lockInterruptibly();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public boolean tryLock()
        {
            aboutToAcquire(readWriteLock);
            try
            {
                return super.tryLock();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException
        {
            aboutToAcquire(readWriteLock);
            try
            {
                return super.tryLock(timeout, unit);
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }

        @Override
        public void unlock()
        {
            try
            {
                super.unlock();
            }
            finally
            {
                lockStateChanged(readWriteLock);
            }
        }
    }
}
